package com.zpark.test;

import java.util.Scanner;

/**
 * 杀人游戏
 * 复杂度为O(n * m)
 */

public class demo03 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入猴子总数");
        int n = scan.nextInt();// n代表猴子总数
        System.out.println("请输入要数到几");
        int m = scan.nextInt();// m代表数到几
        int[] monkeys = new int[n];
        // index表示正数数的猴子，count计数器， 表示1-m报数；pNum表示存活的猴子数，一开始所有的猴子都存活
        int index = -1, count, pNum = n;
        // 只要猴子数多于一只，游戏就一直进行
        while (pNum > 1){
            count = 0;
            // 表示1数到m的过程
            while (count != m){
                index = (index + 1) % n;
                if (monkeys[index] == 0){
                    count++;
                    if (count == m)
                        monkeys[index] = 1;
                }
            }
            pNum--;
        }
        // 将最后的猴子输出
        for (int i = 0;i < n; i++){
            if (monkeys[i] == 0){
                System.out.printf("第%d只猴子成为猴王！", i + 1);
                break;
            }
        }
    }
}
